package algorithm.sort;


import java.util.Arrays;

//基数排序
public class RadixSort {
    public static void main(String[] args) {
        int[] data =   new int[]{5,3,-1,78,456,999,-999};
        radixSort(data);
        System.out.println(Arrays.toString(data));

    }

    public static void radixSort(int[] data){
        //求出数组中的最大值的位数
        int max = data[0];
        int min = data[0];
        for (int i =0;i<data.length;i++){
            max = Math.max(max,data[i]);
            min = Math.min(min,data[i]);
        }
        if (min<0){//如果最小值小于0，那么把每个数都减去最小值，这样可以保证最小的数是0
            for (int i =0;i<data.length;i++){
                data[i]-=min;
            }
        }
        //这一步很重要！！！！！
        max -= min; //max也要处理！
        int maxLength = (max+"").length();
        //创建10个桶
        int[][] bucket = new int[10][data.length];

        //创建一个一维数组，存放每个桶内元素的个数,因为有10个桶，所以长度为10
        int[] bucketElementCounts = new int[10];
        for (int k=0,n=1;k<maxLength;k++,n*=10){
            for (int i =0;i<data.length;i++){
                int num= data[i]/n%10;
                bucket[Math.abs(num)][bucketElementCounts[Math.abs(num)]] = data[i];
                bucketElementCounts[Math.abs(num)]++;
            }
            //循环10个桶，将桶内的数据拷贝到原数组中
            int index = 0;
            for (int l =0;l<10;l++){
                if (bucketElementCounts[l]!=0){
                    for (int j = 0;j<bucketElementCounts[l];j++){
                        data[index++] = bucket[l][j];
                    }
                }
                bucketElementCounts[l]=0;
            }
        }
        if (min<0){//加回来
            for (int i =0;i<data.length;i++){
                data[i]+=min;
            }
        }
        }

}

